package leetcode_200;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *WordLadder_127 广度遍历
 *describe:用队列 AC 77%
 *2018年5月26日 上午11:06:07
 */
public class WordLadderII_126_ {
	List<List<String>> res=new LinkedList<List<String>>();
	public static void main(String[] args) {
		WordLadderII_126_ test=new WordLadderII_126_();
		List<String> wordList=new ArrayList<String>();
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");
		
		List<String> wordList1=new ArrayList<String>();
		wordList1.add("hot");
		wordList1.add("cog");
		wordList1.add("dog");
		wordList1.add("tot");
		wordList1.add("hog");
		wordList1.add("hop");
		wordList1.add("pot");
		wordList1.add("dot");
		
		List<String> wordList2=new ArrayList<String>();
		wordList2.add("a");
		wordList2.add("b");
		wordList2.add("c");
		
		List<String> wordList3=new ArrayList<String>();
		wordList3.add("ted");
		wordList3.add("tex");
		wordList3.add("red");
		wordList3.add("tax");
		wordList3.add("tad");
		wordList3.add("den");
		wordList3.add("rex");
		wordList3.add("pee");
		
		System.out.println(test.ladderLength("red", "tax", wordList3));
		
		
		System.out.println(test.ladderLength("hit", "cog", wordList));
		System.out.println(test.ladderLength("hot", "dog", wordList1));
		System.out.println(test.ladderLength("a", "c", wordList2));

	}
	
	/**
	 * describe:用层次遍历
	 * 2018年5月26日 上午9:57:31
	 */
	public List<List<String>> ladderLength(String beginWord, String endWord, List<String> wordList) {
		if(wordList==null||!wordList.contains(endWord))
			return this.res;
		int len=beginWord.length();
		int minLen=0;
		Set<String> set=new HashSet<String>(wordList);
		set.remove(beginWord);
		List<String> list=new ArrayList<String>();
		list.add(beginWord);
		this.res.add(list);
		boolean flag=false;
		while(!res.isEmpty()&&!flag) {
			int count=res.size();
			int k=0;
			while(k<count&&!flag) {
				List<String> nowList=this.res.get(0);
				String now=nowList.get(nowList.size()-1);
				for(int i=0;i<len;++i) {
					if(flag)
						break;
					char [] chars=now.toCharArray();
					for(char j='a';j<='z';++j) {
						chars[i]= j; 
						String temp=new String(chars);
						if(set.contains(temp)) {
							if(temp.equals(endWord)) {//如果下一个词能够转换成endWord
								flag=true;
								nowList.add(temp);
								minLen=nowList.size();
								break;
							}
							if(!nowList.contains(temp)) {
								List<String> newList=new ArrayList<String>(nowList);
								newList.add(temp);
								this.res.add(newList);
							}
							//set.remove(temp);
							//System.out.println("In  "+temp );
						}
					}
				}
				++k;
				if(!flag)
					this.res.remove(nowList);
			}
			
		}
		if(!res.isEmpty()) {
			List<List<String>>delete=new ArrayList<List<String>>();
			for(int i=1;i<res.size();++i) {
				List<String> nowList=this.res.get(i);
				if(nowList.size()>minLen-1) {
					delete.add(nowList);
					continue;
				}
				flag=false;
				String now=nowList.get(nowList.size()-1);
				for(int k=0;k<len;++k) {
					char [] chars=now.toCharArray();
					if(flag)//没有必要再判断这个列表了
						break;
					for(char j='a';j<='z';++j) {
						chars[k]= j; 
						String temp=new String(chars);
						if(temp.equals(endWord)) {//如果下一个词能够转换成endWord
								flag=true;//这个列表是对的 不再考虑了
								nowList.add(temp);
								break;
							}
					}
				}
				if(!flag) {
					delete.add(nowList);
				}
			}
			for(int i=0;i<delete.size();++i)
				this.res.remove(delete.get(i));
		}
		
		return this.res;
	
	
    }  

}
